Ghi chú NP (độ phức tạp)

Ghi chú NP (độ phức tạp)

↑ S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof verification and hardness of approximation problems”. Journal of the ACM 45(3):501-555, 1998. ECCC TR98-008.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

x t s Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được	DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP
Các lớp có thể không giải được	UP • NP (NP-đầy đủ · NP-khó · co-NP · co-NP-đầy đủ) • AM • PH • PP • #P (#P-đầy đủ) • IP • PSPACE (PSPACE-đầy đủ)
Các lớp được coi là không giải được	EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc	Cấp bậc đa thức • Cấp bậc hàm mũ • Cấp bậc Grzegorczyk • Cấp bậc số học
Các nhóm các lớp độ phức tạp	DTIME • NTIME • DSPACE • NSPACE • Chứng minh có thể kiểm chứng ngẫu nhiên • Hệ thống chứng minh tương tác

Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

x
t
s

Liên quan

NP NPO 1 NPO Energomash NProtect GameGuard NP-khó Npm (phần mềm) NPO Mashinostroyeniya NP-đầy đủ NP (độ phức tạp) NPO Almaz

Tài liệu tham khảo

WikiPedia: NP (độ phức tạp) http://eccc.uni-trier.de/eccc-reports/1998/TR98-00...